#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode *mis1;
TreeNode *mis2;
TreeNode *pre;

void SetMis(TreeNode *p, TreeNode *c){
    if(!mis2){
        mis2 = p;
        return;
    }
    if(!mis1){
        mis1 = c;
        return;
    }
}

void FindNode(TreeNode *root){
    if(!root)
        return;
    if(root->left){
        FindNode(root->left);
    }
    // visit this
    if(pre){
        // not the first, check
        if(pre->val > root->val){
            SetMis(pre, root);
        }
    }
    pre = root;
    if(root->right){
        FindNode(root->right);
    }
}

void recoverTree(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return;
    mis1 = NULL;
    mis2 = NULL;
    pre = NULL;

   FindNode(root);

   int temp = mis1->val;
   mis1->val = mis2->val;
   mis2->val = mis1->val;

}